package lib

func init() {
	Probs = append(Probs, Problem{
		Num:         315,
		Discription: "数组中每个元素右侧小于该元素的元素个数",
		Level:       3,
		Labels: map[string]int{
			"归并排序": 1,
			"哈希表": 1,
			"索引排序": 1,
		},
	})
}

func CountSmaller(nums []int) []int {
	count := make([]int, len(nums))
	//nums不会发生变化，排序的结果体现在indexes里
	//indexes表示第i位元素排序后应该指向的是nums的第index[i]位元素
	//因为排序后值的位置一直在变，值也可能重复，所以得用index维护一个当前位置和指定的初始索引的映射关系，方便统计count
	index := make([]int, len(nums))
	for i := range nums {
		index[i] = i
	}

	var merge func(int, int)
	//大框架正常的归并排序
	merge = func(start, end int) {
		if start >= end {
			return
		}

		mid := start + (end-start)/2
		merge(start, mid)
		merge(mid+1, end)
		//用temp存储当前排序范围内排序后每个位置的nums里的索引指向
		tempIndex := make([]int, end-start+1)
		i := start
		j := mid + 1
		rightCount := 0
		k := 0
		for i <= mid && j <= end {
			//一定得是<=，因为等于的情况不能算到rightCount里
			if nums[index[i]] <= nums[index[j]] {
				tempIndex[k] = index[i]
				//每当左半段数组有元素被选上，它之前都被选了rightCount个比它小的数组，所以给对应实际索引位置的count加上rightCount
				//之后更大范围内的合并，右半边的元素都是新的，所以不会有重复
				//只需要在左半边的数组的元素被选上统计rightCount
				//因为题目要求的是统计每个元素右侧比该元素小的元素刷量，对于右半边的数组的元素，它们的rightCount在当前范围内只能来自于本身右半边的数组，然而这已经在前一轮合并中统计过了
				count[index[i]] += rightCount
				i++
			} else {
				tempIndex[k] = index[j]
				rightCount++
				j++
			}
			k++
		}

		for i <= mid {
			tempIndex[k] = index[i]
			count[index[i]] += rightCount
			i++
			k++
		}

		for j <= end {
			tempIndex[k] = index[j]
			j++
			k++
		}

		//更新每个位置排序后的实际索引
		for i := range tempIndex {
			index[i+start] = tempIndex[i]
		}
	}

	merge(0, len(nums)-1)
	return count
}